import time

t0 = time.time()


class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.available = []
        self.value = 0


def row_num(p, shudu):
    row = set(shudu[p.y * 9:(p.y + 1) * 9])
    row.remove(0)
    return row


def col_num(p, shudu):
    col = []
    length = len(shudu)
    for i in range(p.x, length, 9):
        col.append(shudu[i])
    col = set(col)
    col.remove(0)
    return col


def block_num(p, shudu):
    block_x = p.x // 3
    block_y = p.y // 3
    block = []
    start = block_y * 3 * 9 + block_x * 3
    for i in range(start, start + 3):
        block.append(shudu[i])
    for i in range(start + 9, start + 9 + 3):
        block.append(shudu[i])
    for i in range(start + 9 + 9, start + 9 + 9 + 3):
        block.append(shudu[i])
    block = set(block)
    block.remove(0)
    return block


def initPoint(shudu):
    pointList = []
    length = len(shudu)
    for i in range(length):
        if shudu[i] == 0:
            p = Point(i % 9, i // 9)
            for j in range(1, 10):
                if j not in row_num(p, shudu) and j not in col_num(p, shudu) and j not in block_num(p, shudu):
                    p.available.append(j)
            pointList.append(p)
    return pointList


def tryInsert(p, sudoku):
    availNum = p.available
    for v in availNum:
        p.value = v
        if check(p, shudu):
            shudu[p.y * 9 + p.x] = p.value
            if len(pointList) <= 0:
                t1 = time.time()
                useTime = t1 - t0
                show(shudu)
                print('\n总用时: %f s' % (useTime))
                break
            p2 = pointList.pop()
            tryInsert(p2, shudu)
            shudu[p2.y * 9 + p2.x] = 0
            shudu[p.y * 9 + p.x] = 0
            p2.value = 0
            pointList.append(p2)
        else:
            pass


def check(p, sudoku):
    if p.value not in row_num(p, sudoku) and p.value not in col_num(p, sudoku) and p.value not in block_num(p, sudoku):
        return True
    else:
        return False
def show(shudu):
    for j in range(9):
        for i in range(9):
            print('%d  ' % (shudu[j * 9 + i]), end='')
        print('')


shudu = [
    9, 7, 0, 4, 0, 0, 0, 0, 0,
    0, 2, 0, 0, 0, 1, 9, 0, 0,
    0, 0, 0, 0, 0, 6, 0, 0, 8,
    0, 0, 5, 0, 0, 9, 0, 0, 0,
    0, 0, 0, 3, 0, 0, 8, 0, 1,
    0, 0, 0, 0, 8, 0, 7, 3, 0,
    5, 0, 0, 0, 0, 0, 0, 0, 9,
    0, 0, 3, 8, 5, 0, 4, 0, 0,
    6, 0, 2, 0, 0, 0, 0, 5, 0
]

pointList = initPoint(shudu)
p = pointList.pop()
tryInsert(p, shudu)
while(True):
    1
